package com.zjoin.study.arithmetic.基础.数组;

/**
 * 类名 删除排序数组中的重复项
 * 描述
 *
 * @Author xwyang
 * @Date 2020/8/14 9:44
 * @Version 1.0
 **/
public class 删除排序数组中的重复项 {
    /**
     * 题设：
     * 给定一个排序数组，你需要在 原地 删除重复出现的元素，
     * 使得每个元素只出现一次，
     * 返回移除后数组的新长度。
     * 注意：
     * 不要使用额外的数组空间，你必须在 原地 修改输入数组
     * 并在使用 O(1) 额外空间的条件下完成。
     * 示例：
     * 给定 nums = [0,0,1,1,1,2,2,3,3,4],
     * 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
     * 你不需要考虑数组中超出新长度后面的元素。
     */
    public static int removeDuplicates(int[] nums) {
        if (nums.length < 0) {
            return -1;
        }
        if (nums.length == 1) {
            return 1;
        }
        int k = 0;
        for (int i = 0; i < nums.length; i++) {
            print(nums);
          
            
            System.out.println("i=" + i);
            int j = i + 1;
            if (j < nums.length && nums[i] >= nums[j]) {
                if (j > k) {
                    k = j + 1;
                }
                for (int x = k ; x < nums.length; x++) {
                    if (nums[i] < nums[x]) {
                        nums[j] = nums[x];
                        k = x;
                        break;
                    }else {
                        k++;
                    }
                    
                }
                if (k >= nums.length) {
                    return i + 1;
                }
                
            }
            
        }
        return nums.length;
    }
    
    public static void main(String[] args) {
//        int[] nums = {1, 1,1};
        int[] nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4,4,4,5,6,6,6,9,9,23,44,57,66,66,88,88,88};
        System.out.println(removeDuplicates(nums));
        System.out.println("-------------------------------------------");
        System.out.println(removeDuplicates2(nums));
    }
    
    private static void print(int[] nums) {
        for (int c : nums) {
            System.out.print(c + ",");
        }
        
    }
    
    public static int removeDuplicates2(int[] nums) {
        if (nums.length == 0) return 0;
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
          
            System.out.println();
            if (nums[j] != nums[i]) {
                i++;
                nums[i] = nums[j];
            }
            print(nums);
        }
        return i + 1;
    }
    
}
